#include <algorithm>
#include <iostream>
#include <random>
#include <sys/types.h>
#include <vector>
using namespace std;

int mergecount(vector<int> &nums, int l, int m, int r) {
  int ans = 0;
  int closure = m + 1;
  for (int i = l; i <= m; ++i) {
    // 重点就是在这里，可以先计数结果，再merge
    while ((closure <= r) && (nums[i] > 2 * nums[closure])) {
      ++closure;
    }
    ans += closure - m - 1;
  }

  vector<int> temp;
  temp.resize(r - l + 1);
  int point = l;
  int point2 = m + 1;
  int pointtemp = 0;
  while (point <= m && point2 <= r) {
    if (nums[point] <= nums[point2]) {
      temp[pointtemp] = nums[point];
      ++point;
    } else {
      temp[pointtemp] = nums[point2];
      ++point2;
    }
    ++pointtemp;
  }
  while (point <= m) {
    temp[pointtemp] = nums[point];
    ++point;
    ++pointtemp;
  }
  while (point2 <= r) {
    temp[pointtemp] = nums[point2];
    ++point2;
    ++pointtemp;
  }
  for (int i = l; i <= r; ++i) {
    nums[i] = temp[i - l];
  }
  return ans;
}

int proc(vector<int> &nums, int l, int r) {
  if (l >= r) {
    return 0;
  }
  int mid = l + ((r - l) >> 1);
  int ans1 = proc(nums, l, mid);
  int ans2 = proc(nums, mid + 1, r);
  int ans3 = mergecount(nums, l, mid, r);
  return ans1 + ans2 + ans3;
}

int main() {
  int len = 50;
  int min = -100;
  int max = 100;
  int timety = 20;
  int tim = 0;
  while (tim < timety) {
    random_device seed;      // 硬件生成随机数种子
    ranlux48 engine(seed()); // 利用种子生成随机数引擎
    uniform_int_distribution<> distrib(min,
                                       max); // 设置随机数范围，并为均匀分布
    vector<int> a;
    for (int i = 0; i < len; ++i) {
      int random = distrib(engine);
      a.push_back(random);
    }
    vector<int> b = a;
    vector<int> c = a;
    int al = proc(a, 0, a.size() - 1);

    sort(b.begin(), b.end());
    for (int i = 0; i < a.size(); ++i) {
      if (a[i] != b[i]) {
        cout << "err" << endl;
      }
    }

    int ansc = 0;
    for (int i = 0; i < c.size(); ++i) {
      for (int j = i + 1; j < c.size(); ++j) {
        if (c[i] > 2 * c[j]) {
          ++ansc;
        }
      }
    }
    if (al != ansc) {
      cout << "count err" << al << " " << ansc << endl;
      for (auto p = c.begin(); p != c.end(); ++p) {
        cout << *p << " ";
      }
      cout << endl;
    }
    ++tim;
    cout << "Finished" << endl;
  }
}
